#include<iostream>
#include<vector>

using namespace std;


void dfs(vector<int>& nums, int sum, int pos);

vector<vector<int>> ret;
vector<int> path;
int aim;
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    aim = target;
    dfs(candidates, 0, 0);
    return ret;
}
void dfs(vector<int>& nums, int sum, int pos)
{
    if (sum >= aim)
    {
        if (sum == aim) ret.push_back(path);
        return;
    }

    for (int i = pos; i < nums.size(); i++)
    {
        path.push_back(nums[i]);
        //sum += nums[i];
        dfs(nums, sum += nums[i], i);
        path.pop_back();
    }
}

int main()
{
    vector<int> nums = { 2,3,6,7 };
    
    combinationSum(nums, 7);
    return 0;
}



class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;
    int aim;
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        aim = target;
        dfs(candidates, 0, 0);
        return ret;
    }
    void dfs(vector<int>& nums, int sum, int pos)
    {
        if (sum >= aim)
        {
            if (sum == aim) ret.push_back(path);
            return;
        }

        for (int i = pos; i < nums.size(); i++)
        {
            path.push_back(nums[i]);
            dfs(nums, sum + nums[i], i);
            path.pop_back();
        }
    }
};